package com.erbao.datastructurearithmetic.base;

import com.erbao.datastructurearithmetic.RandomUtil;
import com.erbao.dp.itrator.ArrayList_;
import com.erbao.dp.itrator.Iterator_;

import java.util.*;

/**
 * @author CaoBaoYin
 * @since 21/11/9 15:14
 */
public class Class02 {

    public static void main(String[] args) {
        Class02 c = new Class02();
        /*int maxValue = 10;
        for (int i = 0; i < 100000; i++) {
            Node<Integer> head = c.generateSingleLink(10, maxValue);
            ArrayList_<Integer> list = c.linkToList(head);
            Integer value = (int) (Math.random() * maxValue);

            // head.show();
            // System.out.println(list);
            // System.out.println("删除：".concat(value.toString()));

            head = c.remove(head, value);
            list.remove(value);

            if (! c.equals(head, list)) {
                head.show();
                System.out.println(list);
                System.out.println("bad");
                return;
            }
        }*/

        /*Stack<Integer> s = new Stack<>();
        TwoQueueStack<Integer> tqs = new TwoQueueStack<>();
        for (int i = 0; i < 1000000; i++) {

            double op = Math.random();
            if (op < 0.5) {
                Integer value = (int) (Math.random() * 100);
                s.push(value);
                tqs.push(value);
            } else {
                if (!tqs.isEmpty()) {
                    Integer poll = s.pop();
                    Integer poll1 = tqs.pop();
                    if (!poll.equals(poll1)) {
                        System.out.println(s);
                        System.out.println(tqs);
                        System.out.println("bad");
                        return;
                    }
                }
            }

        }
        System.out.println(s);
        System.out.println(tqs);*/

        /*MinStack stack = new MinStack();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 1000000; i++) {
            double op = Math.random();
            if (op < 0.5) {
                Integer value = (int) (Math.random()*100);
                stack.push(value);
                list.add(value);
            } else {
                if (stack.isEmpty() && list.isEmpty()) {
                    continue;
                }
                Integer value = stack.pop();
                list.remove(value);
            }

            if (stack.isEmpty() && list.isEmpty()) {
                continue;
            }

            Integer min = stack.getMin();
            Collections.sort(list);
            Integer min2 = list.get(0);

            if (! min.equals(min2)) {
                System.out.println(list);
                System.out.println(stack);
                System.out.println("bad");
                return;
            }
        }*/

        for (int i = 0; i < 1000000; i++) {
            int[] arr = RandomUtil.lenRandomAndValueRandom(100, 100);
            if (arr.length < 1) continue;

            int max = c.max(arr);
            Arrays.sort(arr);
            if (max != arr[arr.length-1]) {
                System.out.println(arr);
                System.out.println("bad");
            }
        }

        System.out.println("nice");
    }

    public <V> boolean equals(Node<V> head, ArrayList_<V> list) {
        if (head == null) return list==null || list.isEmpty();

        Node<V> cursor = head;
        Iterator_<V> it = list.iterator();
        while (cursor != null) {
            if (! cursor.value.equals(it.next())) {
                return false;
            }
            cursor = cursor.next;
        }
        return true;
    }

    public int max (int[] arr) {
        if (arr==null || arr.length==0) throw new IllegalArgumentException("数组为空");

        if (arr.length == 1) return arr[0];

        return processMax (arr, 0, arr.length-1);
    }

    private int processMax(int[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }

        int mid = l + ((r-l) >> 1);
        int left = processMax(arr, l, mid);
        int right = processMax(arr, mid+1, r);
        return Math.max(left, right);
    }

    /**
     * 单链表转为list存储值
     * @param head 头结点
     * @param <V> 值的类型
     * @return liked list
     */
    public <V> ArrayList_<V> linkToList (Node<V> head) {
        ArrayList_<V> list = new ArrayList_<V>();

        Node<V> cursor = head;
        while (cursor != null) {
            list.add(cursor.value);
            cursor = cursor.next;
        }

        return list;
    }

    /**
     * 产生随机单链表
     * @param length 长度
     * @param maxValue less than
     * @return 头结点
     */
    public Node<Integer> generateSingleLink (int length, int maxValue){
        if (length == 0) return null;

        Node<Integer> head = new Node<>();
        head.value = (int) (Math.random()*maxValue);

        Node<Integer> cursor = head;
        for (int i = 1; i < length; i++) {
            Node<Integer> node = new Node<>();
            node.value = (int) (Math.random()*maxValue);
            cursor.next = node;
            cursor = cursor.next;
        }

        return head;
    }

    /**
     * 删除单链表中的一个值
     * @param head 链表头结点
     * @param value 值
     * @param <V> 值的类型
     * @return 链表头结点
     *
     * 这个值可能在链表的头或尾或中间，也可能有多个结点
     */
    public <V> Node<V> remove (Node<V> head, V value) {
        if (head == null) return head;

        /*循环目的：头结点如果出现连续相等，头结点指针向后移除，则前面的结点就会被自动GC
        * 头结点若相等就会被移除*/
        while (head != null) {
            // 遍历链表，找到第一个与value不等的节点
            if (!head.value.equals(value)) {
                break;
            }
            head = head.next;
        }

        Node<V> pre = head;
        Node<V> cursor = head.next;
        /*支持中间结点和尾结点移除*/
        while (cursor != null) {
            if (cursor.value.equals(value)) {
                pre.next = cursor.next;
            } else {
                pre = pre.next;
            }

            cursor = cursor.next;
        }

        return head;
    }
}

class Stack_ {
    Object[] objs;
    int size;

    public Stack_(int maxCapacity) {
        objs = new Object[maxCapacity];
    }

    public Object push (Object o) {
        objs[size++] = o;
        return o;
    }

    public Object pop () {
        return objs[--size];
    }

    public Object peek () {
        return objs[size-1];
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

class TwoQueueStack <E> {
    private Queue<E> q1 = new LinkedList<>();
    private Queue<E> q2 = new LinkedList<>();

    public boolean push (E e) {
        // 找出不空的队列，入队
        Queue<E> q = q1.isEmpty() ? q2 : q1;
        q.offer(e);
        return true;
    }

    /**
     * 将有数据的队列倒倒无数据的队列，剩最后一个值pop出去
     */
    public E pop () {
        Queue<E> noDataQueue = q1.isEmpty() ? q1 : q2;
        Queue<E> dataQueue = noDataQueue==q1 ? q2 : q1;

        while (dataQueue.size() > 1) {
            noDataQueue.offer(dataQueue.poll());
        }

        return dataQueue.poll();
    }

    /**
     * 相当于倒数据过程中，最后一个数拿出来看一下，再放进去。前面几个数都是直接放进去，没有看。
     */
    public E peek() {
        E e = pop();
        push(e);
        return e;
    }

    public boolean isEmpty () {
        return q1.isEmpty() && q2.isEmpty();
    }

    @Override
    public String toString() {
        return "TwoQueueStack{" +
                "q1=" + q1 +
                ", q2=" + q2 +
                '}';
    }
}

class TwoStackQueue <E> {

    private Stack<E> pushStack;
    private Stack<E> popStack;

    public TwoStackQueue() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }

    private void pushToPop () {
        // pop栈为空才能往pop倒数据
        if (popStack.isEmpty()) {
            // 倒数据必须一次性倒完
            while (! pushStack.empty()) {
                popStack.push(pushStack.pop());
            }
        }
    }

    public boolean offer (E e) {
        /*入栈前不用从pop倒到push，因为只要遵循：
        * 1.pop栈为空才能往pop倒数据
        * 2.倒数据必须一次性倒完
        * 数据的顺序不会乱*/
        pushStack.push(e);
        pushToPop();
        return true;
    }

    public E poll () {
        if (this.empty()) {
            throw new EmptyStackException();
        }
        pushToPop();
        return popStack.pop();
    }

    public E peek () {
        if (this.empty()) {
            throw new EmptyStackException();
        }
        pushToPop();
        return popStack.peek();
    }

    public boolean empty () {
        return pushStack.empty() && popStack.empty();
    }

    @Override
    public String toString() {
        return "TwoStackQueue{" +
                "pushStack=" + pushStack +
                ", popStack=" + popStack +
                '}';
    }
}


class Queue_ {
    Object[] objs;
    int size;
    int pushIndex;
    int popIndex;

    public Queue_(int maxCapacity) {
        objs = new Object[maxCapacity];
    }

    public boolean offer (Object o ){
        ensureCapacity();

        objs[pushIndex] = o;
        pushIndex = nextIndex(pushIndex);
        size ++;

        return true;
    }

    private int nextIndex(int index) {
        return index +1 < objs.length ? index +1 : 0;
    }

    public Object poll () {
        if (isEmpty()) {
            throw new RuntimeException("队列已空");
        }

        Object obj = objs[popIndex];
        popIndex = nextIndex(popIndex);
        size -- ;
        return obj;
    }

    public void ensureCapacity(){
        if (size >= objs.length) {
            throw new RuntimeException("空间已满");
        }
    }

    public boolean isFull(){
        return size >= objs.length;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    @Override
    public String toString() {
        return "Queue_{" +
                "objs=" + Arrays.toString(objs) +
                ", size=" + size +
                ", pushIndex=" + pushIndex +
                ", popIndex=" + popIndex +
                '}';
    }
}

class Node<V> {
    public Node<V> prev;//上一个节点
    public Node<V> next;//下一个节点
    public V value;//值

    public void show() {
        Node<V> cursor = this;
        while (cursor != null) {
            System.out.print(cursor.value + " --> ");
            cursor = cursor.next;
        }
        System.out.println("null");
    }
}

class MinStack {
    private Stack<Integer> minStack = new Stack<>();
    private Stack<Integer> dataStack = new Stack<>();

    /**
     * 压栈时，首先压入数据栈，然后数据栈顶和最小值栈顶比较，最小值栈压入较小的值。
     * 两个栈始终是同样高度
     * @param num
     * @return
     */
    public Integer push (int num) {
        if (minStack.isEmpty()) {
            minStack.push(num);
        } else {
            minStack.push(Math.min(minStack.peek(), num));
        }
        dataStack.push(num);
        return num;
    }

    public Integer pop (){
        minStack.pop();
        return dataStack.pop();
    }

    public Integer getMin() {
        return minStack.peek();
    }

    public boolean isEmpty () {
        return minStack.isEmpty() && dataStack.isEmpty();
    }

    @Override
    public String toString() {
        return "MinStack{" +
                "minStack=" + minStack +
                ", dataStack=" + dataStack +
                '}';
    }
}